'''
https://leetcode.cn/problems/merge-k-sorted-lists/
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。
'''

from typing import List
import heapq
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not list:
            return None
        l = ListNode(-1)
        p = l
        pq = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(pq,(lists[i].val,i))
                lists[i] = lists[i].next
        while pq:
            val,idx = heapq.heappop(pq)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(pq,(lists[idx].val,idx))
                lists[idx] = lists[idx].next
        return l.next
    
    def mergeKLists2(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0: return []
        arr = lists[0]
        for li in lists[1:]:
            arr = self.mergeTwoLists(arr,li)
        return arr

    def mergeTwoLists(self,list1:ListNode, list2:ListNode):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        newList = ListNode(-1)
        temp = newList
        p = list1
        q = list2
        while p and q:
            if p.val > q.val:
                temp.next = q
                q = q.next
            else:
                temp.next = p
                p = p.next
            temp = temp.next
        if p:
            temp.next = p
        if q:
            temp.next = q
    
        return newList.next 

